package cs275.ants.graph;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Random;
import java.util.Stack;

public class MazeGenerator {

	private Random generator = new Random((new Date()).getTime());

	/**
     * Generate a maze randomly
     */
    public Maze generate(int cols, int rows)
    {
    	MazeCell[][] cells = new MazeCell[rows][cols];
    	Stack<MazeCell> cellStack = new Stack<MazeCell>();
    	int visitedCells = 1;
    	
    	for (int i = 0; i < rows; i++) {
    		for (int j = 0; j < cols; j++)
    		{
//    			cells[i][j] = new MazeCell(width, height);
    			cells[i][j] = new MazeCell();
    			cells[i][j].row = i;
    			cells[i][j].column = j;
    		}
    	}

    	MazeCell currentCell = cells[0][0];
    	int totalCells = cols * rows;
		while (visitedCells < totalCells) // Total Cells
		{
			// get a list of the neighboring cells with all walls intact
			List<MazeCell> AdjacentCells = getNeighborsWithWalls(cols, rows, cells, currentCell);
			// test if a cell like this exists
			if (AdjacentCells.size() > 0) {
				// yes, choose one of them, and knock down the wall between it
				// and the current cell
				int randomCell = generator.nextInt(AdjacentCells.size());
				MazeCell theCell = AdjacentCells.get(randomCell);
				currentCell.knockDownWall(theCell);
				cellStack.push(currentCell); // push the current cell onto the
				// stack
				currentCell = theCell; // make the random neighbor the new
				// current cell
				visitedCells++;
			} else {
				// No cells with walls intact, pop current cell from stack
				currentCell = cellStack.pop();
			}
		}
		return new Maze(cols, rows, cells);
    }

    private List<MazeCell> getNeighborsWithWalls(int width, int height, MazeCell[][] cells, MazeCell aCell)
    {
    	List<MazeCell> neighbors = new ArrayList<MazeCell>();
    	
    	// find neighbor cells with walls intact
    	for (int countRow = -1; countRow <= 1; countRow++)
    		for (int countCol = -1; countCol <= 1; countCol++)
    		{
    			int row = aCell.row + countRow; 
    			int col = aCell.column + countCol; 
    			
    			if ((row < height) &&
    				(col < width) &&
    				(row >= 0) &&
    				(col >= 0) &&
    				((countCol == 0) || (countRow == 0)) &&
    				(countRow != countCol)
    			)
    			{
    				if (cells[row][col].hasAllWalls())
    				{
    					neighbors.add(cells[row][col]);
    				}
    			}
    		}

    	return neighbors;
    }
}
